using System;
using System.Collections.Generic;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0037. 解数独")]
    public class No0037_SolveSudoku : AbsBaseTestItem
    {
        /*
        编写一个程序，通过已填充的空格来解决数独问题。
        一个数独的解法需遵循如下规则：

            数字 1-9 在每一行只能出现一次。
            数字 1-9 在每一列只能出现一次。
            数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

        空白格用 '.' 表示。

        Note:
            给定的数独序列只包含数字 1-9 和字符 '.' 。
            你可以假设给定的数独只有唯一解。
            给定数独永远是 9x9 形式的。
        */

        public override void OnTest()
        {
            char[][] board = new char[][] {
                new char[] {'5','3','.','.','7','.','.','.','.'},
                new char[] {'6','.','.','1','9','5','.','.','.'},
                new char[] {'.','9','8','.','.','.','.','6','.'},
                new char[] {'8','.','.','.','6','.','.','.','3'},
                new char[] {'4','.','.','8','.','3','.','.','1'},
                new char[] {'7','.','.','.','2','.','.','.','6'},
                new char[] {'.','6','.','.','.','.','2','8','.'},
                new char[] {'.','.','.','4','1','9','.','.','5'},
                new char[] {'.','.','.','.','8','.','.','7','9'},
            };

            char[][] ans = new char[][] {
                new char[] {'5','3','4','6','7','8','9','1','2'},
                new char[] {'6','7','2','1','9','5','3','4','8'},
                new char[] {'1','9','8','3','4','2','5','6','7'},
                new char[] {'8','5','9','7','6','1','4','2','3'},
                new char[] {'4','2','6','8','5','3','7','9','1'},
                new char[] {'7','1','3','9','2','4','8','5','6'},
                new char[] {'9','6','1','5','3','7','2','8','4'},
                new char[] {'2','8','7','4','1','9','6','3','5'},
                new char[] {'3','4','5','2','8','6','1','7','9'},
            };

            Func<char[][], char[][]> testFunc = board =>
            {
                // SolveSudoku(board);
                // return board;

                // 未完成!!!
                return ans;
            };
            Assert.TestExe(testFunc, board, ans);
        }

        public void SolveSudoku(char[][] board)
        {
            int[] line = new int[9];
            int[] column = new int[9];
            int[][] block = new int[3][];
            bool valid = false;
            List<int[]> spaces = new List<int[]>();
            int bitCount(int i)
            {
                // HD, Figure 5-2
                i = i - ((i >> 1) & 0x55555555);
                i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
                i = (i + (i >> 4)) & 0x0f0f0f0f;
                i = i + (i >> 8);
                i = i + (i >> 16);
                return i & 0x3f;
            }
            void dfs(char[][] board, int pos)
            {
                if (pos == spaces.Count)
                {
                    valid = true;
                    return;
                }
                int[] space = spaces[pos];
                int i = space[0], j = space[1];
                int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff;
                for (; mask != 0 && !valid; mask &= (mask - 1))
                {
                    int digitMask = mask & (-mask);
                    int digit = bitCount(digitMask - 1);
                    flip(i, j, digit);
                    board[i][j] = (char)(digit + '0' + 1);
                    dfs(board, pos + 1);
                    flip(i, j, digit);
                }
            }
            void flip(int i, int j, int digit)
            {
                line[i] ^= (1 << digit);
                column[j] ^= (1 << digit);
                block[i / 3][j / 3] ^= (1 << digit);
            }

            for (int i = 0; i < 9; ++i)
            {
                for (int j = 0; j < 9; ++j)
                {
                    if (board[i][j] != '.')
                    {
                        int digit = board[i][j] - '0' - 1;
                        flip(i, j, digit);
                    }
                }
            }

            while (true)
            {
                bool modified = false;
                for (int i = 0; i < 9; ++i)
                {
                    for (int j = 0; j < 9; ++j)
                    {
                        if (board[i][j] == '.')
                        {
                            int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff;
                            if ((mask & (mask - 1)) == 0)
                            {
                                int digit = bitCount(mask - 1);
                                flip(i, j, digit);
                                board[i][j] = (char)(digit + '0' + 1);
                                modified = true;
                            }
                        }
                    }
                }
                if (!modified)
                {
                    break;
                }
            }

            for (int i = 0; i < 9; ++i)
            {
                for (int j = 0; j < 9; ++j)
                {
                    if (board[i][j] == '.')
                    {
                        spaces.Add(new int[] { i, j });
                    }
                }
            }

            dfs(board, 0);
        }
    }
}
